package longestcommonsubstring

// 找到两个字符串的最长公共子串（Longest Common Substring）, 使用暴力枚举的方法
//  1. 遍历字符串a的所有可能的子串
//  2. 对于每个子串，检查它是否在字符串b中存在
//  3. 如果存在，返回该子串
//  4. 如果不存在，继续检查下一个子串
//  5. 如果没有找到，返回空字符串
//  6. 注意：这个方法的时间复杂度是 O(n^3)，因为我们需要遍历字符串a的所有可能的子串，
//     对于每个子串，我们需要检查它是否在字符串b中存在，这个检查的时间复杂度是 O(n)，所以总的时间复杂度是 O(n^3)
func longestCommonSubstringIter(a, b string) string {
	maxSubStrLen := 0
	targetSubstr := ""
	// 遍历字符串a的所有可能的子串
	for i := 0; i < len(a); i++ {
		for j := i + 1; j <= len(a); j++ {
			// 对于每个子串，检查它是否在字符串b中存在
			// 这里的子串是 a[i:j]，注意 j 是不包含的
			// 例如 a[0:3] 是从下标0到下标2的子串
			// 也就是 a[0:3] = a[0] + a[1] + a[2]
			substr := a[i:j]
			// 如果子串在字符串b中存在，返回该子串
			if contains(b, substr) {
				if len(substr) > maxSubStrLen {
					maxSubStrLen = len(substr)
					targetSubstr = substr
				}
			}
		}
	}

	return targetSubstr
}

func contains(s, substr string) bool {
	// 遍历字符串s，检查是否包含子串
	// i的最大值是 len(s)-len(substr), 因为构造子串使用的是 [i, i+len] 的方法，在移动i的过程中，i+len 不能超过len(s)
	for i := 0; i <= len(s)-len(substr); i++ {
		if s[i:i+len(substr)] == substr {
			return true
		}
	}
	return false
}
